- Entstehung
- Standard PSO
- Beispiel 2D
- Nebenbedingungen
- Beispiel 2D mit Nebenbedingungen
- Konvergenz
- Vor- und Nachteile
- Fazit
2022-11-07
Optimierungsproblem:
Vehalten des PSO:
Initialisiere zufällige Positionen \(x^{k, i}\) und Richtungsvektoren \(v^{k, i}\) der Partikel \(k\) in Iteration \(i=0\)
Evaluiere die Kostenfunktion mit der Position jedes Partikels
Speicher die bisher beste Position in \(g_{best}^i\)
Speicher die bisher beste Position pro Partikel in \(p_{best}^{k,i}\)
Iterationsschritt \(i \rightarrow i+1\) pro Partikel \(k\): \[ \begin{aligned} v^{k, i+1} &= w \cdot v^{k, i} + c_p \cdot r_1 \cdot (p_{best}^{k,i}-x^{k,i}) + c_g \cdot r_2 \cdot (g_{best}^{k,i}-x^{k,i}) \\ x^{k, i+1} &= x^{k, i} + v^{k, i+1} \end{aligned} \]
Wiederhole Schritt 2-5 bis die Abbruchbedingung erreicht ist
Zielfunktion:
\[
\begin{aligned}
f(x, y) =& -20\cdot e^{-0.2 \cdot \sqrt{0.5 \cdot ((x-1)^2 + (y-1)^2)}} \\
& \ - e^{0.5 \cdot ( cos(2\cdot \pi \cdot x) + cos(2\cdot \pi \cdot y))} + e + 20
\end{aligned}
\] Aufgabe:
Minimiere \(f(x,y)\) mit \(-10 \leq x \leq 10\) und \(-10 \leq y \leq 10\)
Beispiele:
Methoden:
Alte Zielfunktion: \(f(x)\) mit \(f: \mathbb{R}^n \rightarrow \mathbb{R}\)
Bruch von Nebenbedingungen: \(g(x)\) mit \(g(x) \geq 0 \ \forall x \in \mathbb{R}^n\)
Neue Zielfunktion: \(z(x) = f(x) + g(x)\)
Beispiel für gängige Nebenbedingungen: \[ A^T \times x \geq b_0 \] Dann könnte \(g(x)\) wie folgt aussehen: \[ g(x) = ||\vec{\lambda}( A^T \times x - b_0 )||_2^2 \] mit elementweiser Anwendung von \[ \lambda(x) = \begin{cases} 0 &\text{ if }x \geq 0\\ x &\text{ if }x < 0 \end{cases} \]
Gomez and Levy function (modified)
Convergence Analysis for Particle Swarm Optimization (von Berthold Schmitt)
“Obwohl das PSO in zahlreichen realen Anwendungen verwendet wird, haben theoretische Betrachtungen bisher nur einige wenige Teilaspekte des Algorithmus erklärt. Ein solcher Aspekt, mit dem sich viele Wissenschaftler auseinandersetzen, ist das Phänomen der Konvergenz des Partikelschwarms. Das bedeutet, dass die Partikel gegen einen Punkt im Suchraum konvergieren. Insbesondere konnten notwendige und hinreichende Bedingungen an die Schwarmparameter ermittelt werden, unter denen Konvergenz gewährleistet ist. Allerdings ist bis jetzt kein theoretisches Resultat über die Qualität dieses Grenzwertes bekannt, das für den unmodizierten PSO-Algorithmus in einer allgemeineren Situation als beispielsweise nur für genau eine Zielfunktion bewiesen werden konnte.”
\(f=\) 0.9033333
Nachteile:
Vorteile: